Wellcome to Open Reading Group's library,

  You can find here all papers liked or uploaded by Open Reading Group
  together with brief user bio and description of her/his academic activity.

### Upcoming readings: No upcoming readings for now... ### Past Readings: - 21/05/2018 [Graph Embedding Techniques, Applications, and Performance: A Survey](https://papers-gamma.link/paper/52) - 14/05/2018 [A Fast and Provable Method for Estimating Clique Counts Using Turán’s Theorem](https://papers-gamma.link/paper/24) - 07/05/2018 [VERSE: Versatile Graph Embeddings from Similarity Measures](https://papers-gamma.link/paper/48) - 30/04/2018 [Hierarchical Clustering Beyond the Worst-Case](https://papers-gamma.link/paper/45) - 16/04/2018 [Scalable Motif-aware Graph Clustering](https://papers-gamma.link/paper/18) - 02/04/2018 [Practical Algorithms for Linear Boolean-width](https://papers-gamma.link/paper/40) - 26/03/2018 [New Perspectives and Methods in Link Prediction](https://papers-gamma.link/paper/28/New%20Perspectives%20and%20Methods%20in%20Link%20Prediction) - 19/03/2018 [In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond](https://papers-gamma.link/paper/37) - 12/03/2018 [Diversity is All You Need: Learning Skills without a Reward Function](https://papers-gamma.link/paper/36) - 05/03/2018 [When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors](https://papers-gamma.link/paper/23) - 26/02/2018 [Fast Approximation of Centrality](https://papers-gamma.link/paper/35/Fast%20Approximation%20of%20Centrality) - 19/02/2018 [Indexing Public-Private Graphs](https://papers-gamma.link/paper/19/Indexing%20Public-Private%20Graphs) - 12/02/2018 [On the uniform generation of random graphs with prescribed degree sequences](https://papers-gamma.link/paper/26/On%20the%20uniform%20generation%20of%20random%20graphs%20with%20prescribed%20d%20egree%20sequences) - 05/02/2018 [Linear Additive Markov Processes](https://papers-gamma.link/paper/21/Linear%20Additive%20Markov%20Processes) - 29/01/2018 [ESCAPE: Efficiently Counting All 5-Vertex Subgraphs](https://papers-gamma.link/paper/17/ESCAPE:%20Efficiently%20Counting%20All%205-Vertex%20Subgraphs) - 22/01/2018 [The k-peak Decomposition: Mapping the Global Structure of Graphs](https://papers-gamma.link/paper/16/The%20k-peak%20Decomposition:%20Mapping%20the%20Global%20Structure%20of%20Graphs)
☆
On the uniform generation of random graphs with prescribed degree sequences

Comments:

Short and clear paper to understand important problems encountered when generating a random graph on a typical example: matching methods are often biased (when possible), switching methods are safer but not controlled in terms of mixing time. __Summary__ This article focuses on the uniform generation of simple graphs (no self-loops, no multiple edges) with a prescribed degree distribution. The graphs considered here are directed, but the generalization to the undirected case is straightforward. Uniform generation means that all graphs have the same probability to be generated. 3 methods are compared: - matching (= configuration model) - switching (= basic edge switching method) - go-with-the-winners (new, derived from matching) _switching method_ - draw two random arcs - switch their ends - iterate advantage: if we iterate a sufficient number of times, the graph obtained is uniformly random drawback: we don't know theoretically what is this sufficient number of times... _matching method_ - each node is given in-stubs and out-stubs corresponding to its in- and out-degree - in-stubs and out-stubs are paired randomly - (strong version) if a multi-edge is created the graph is discarded, and restart advantage: the graph obtained is uniformly random drawback: very high probability to restart with heavy-tailed dd weak version (the one used in practice): the graph is not discarded, but the edge is reconnected elsewhere. drawback: the generation is biased _go with the winners_ - starting from a population of graphs (with the right dd) - same principle as the matching algorithm - a graph is discarded if there is a loop or a multi-edge created during the process - but to compensate the drop in number in the population, surviving graphs are cloned and they are given a weight to compensate for their over-representation in the final sample _Experimental results_ On a set of toy-graphs for which all elements are known, they show that there is a sampling bias with the matching method When sampling real classic networks (yeast etc), the bias with the matching algorithm is not detected. In terms of computation speed matching > switching >> gwtw.
Open Reading Group at 2018-05-10 16:51:28
Read the paper, add your comments…
☆
Indexing Public-Private Graphs

Comments:

### Dynamic setting: One of the motivations for the suggested framework is related to the dynamic nature of the reachability graph. However, the suggested framework does not seem to be particularly effective in a dynamic setting (need to recompute the sets "S" from scratch if the reachability graph is modified). Recent work is dedicated to solving the k-center problem in a dynamic setting: "Fully Dynamic k-Center Clustering, Chan et al., WWW2018". The "asymmetric k-center problem" being a subproblem solved in the suggested framework, a more efficient algorithm in a dynamic setting seems possible. ### Effectiveness of greedy: Nice to see that the greedy heuristic leads to a very good approximation on real-world instances for the considered problem (the exact result is known solving an integer program). On the contrary, an algorithm (Ullman and Yannakakis) having good theoretical guarantees performs poorly on the same real-world instances. ### Typos: - "In Table 6.4, the column labeled...": should be "In Table 2, ..."
Open Reading Group at 2018-05-10 16:51:28
Read the paper, add your comments…
☆
Fast Approximation of Centrality

Comments:

Read the paper, add your comments…
Pages: 1 2 3 4 5 6 7 8 9 10 11 12